
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include<functional>
#include<set>
#include<stack>
#include<math.h>

#define MAXV 5


/**
 *  请设计算法：int uniquely(MGraph G)。
    判定G是否存在唯一的拓扑序列，若是则返回1，否则返回0。
    要求:
    （1）给出算法的基本设计思想（4分）
    （2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释（9分）
 */

typedef struct //图的类型定义
{
    int numVertices, numEdges; //图的顶点数和有向边数
    char verticesList[MAXV]; //项点表，MAXV为以定义常量
    int Edge[MAXV][MAXV]; //知接矩阵
}MGraph;

/// @brief 获取点i的入度,对应邻接矩阵来讲，点i的入度就是矩阵左下角第i列的非零的元素个数
/// @param MGraph g 图
/// @param int i 待计算的节点
/// @return 节点i的入度
int getInDegree(MGraph g,int i){
    int count=0;//记录 入 的节点个数
    for(int x=i;x<MAXV;x++){
        if(g.Edge[x][i]!=0){
            count++;
        }
    }
    return count;
}

/// @brief 获取入度为0的节点
/// @return -1表示有多个入度为0的节点，也就是拓扑排序不唯一 ; -2表示处理完毕;其他情况就是入度为0的节点的编号
int getZero(MGraph G){
    int count=0;//记录入度为0的节点的个数
    for(int i=0;i<MAXV;i++){
        int res=getInDegree(G,i);
        if(res==0){
            count++;
        }
    }
    //如果有多个入度为0的节点
    if(count>1){
        return -1;
    }
    //count如果为0，在题目保证没有环的情况下，就表示处理完毕了
    else if(count==0){
        return -2;
    }else{//count=1的情况，此时需要继续处理，吧这个节点拿出来
        //此时再遍历一遍
        for(int i=0;i<MAXV;i++){
            int res=getInDegree(G,i);
            if(res!=0){
                return i;
            }
        }
    }
}

/// @brief 将i从图中删除，并且把他指向的那些节点的入度-1
/// @param g 
/// @param i 
void remove(MGraph* g,int i ){
    for(int j=0;j<MAXV;j++){
        g->Edge[i][j]=0;//把入度置为0
    }
}
//能否优化一些操作？
bool uniquely(MGraph G){

    //使用队列这个数据结构
    //只需要计算一次度数就可以了
    while(true){
        int res=getZero(G);
        if(res==-1){
            return false;
        }else if(res==-2){
            return true;
        }else{
            int node_index=res;
            remove(&G,node_index);
        }
    }
    

}